Năm 1771, khởi nghĩa Tây Sơn bùng nổ ở Quy Nhơn (Đàng Trong), nhiều lần đánh được quân chúa Nguyễn. Nhân cơ hội này, năm 1774 chúa Tĩnh Đô vương Trịnh Sâm sai quận Việp Hoàng Ngũ Phúc làm thống tướng, đem quân vào Nam đánh Thuận Hóa, diệt họ Nguyễn. Nguyễn Hữu Chỉnh đi theo làm thư ký tại quân doanh của quận Việp. Quân Lê-Trịnh đánh như cuốn chiếu, lấy hết đất Thuận Hóa, rồi ập xuống Quảng Nam đánh bại quân Tây Sơn ở trận Cẩm Sa. Thủ lĩnh Tây Sơn Nguyễn Nhạc bị quân Lê-Trịnh và quân Nguyễn đánh kẹp từ 2 đầu Quảng Nam và Phú Yên, nên sai Phan Văn Tuế đem vàng lụa đến đầu hàng Lê-Trịnh và xin làm tiền khu đánh Nguyễn. Quận Việp dâng tờ biểu xin chúa phong Nguyễn Nhạc làm tiền phong tướng quân, rồi sai Nguyễn Hữu Chỉnh mang sắc, ấn, cờ và kiếm ban cho Nguyễn Nhạc. Theo các sách Hoàng Lê nhất thống chí và Khâm định Việt sử thông giám cương mục (bộ chính sử soạn vào thời Nguyễn Dực Tông 1847-83) soạn, Nguyễn Hữu Chỉnh ăn nói trôi chảy nên rất được Nguyễn Nhạc nể trọng.

Cuối năm 1775, quận Việp thu quân về Bắc, giao cho Nguyễn Nhạc diệt chúa Nguyễn. Không lâu sau, quận Việp chết. Nguyễn Hữu Chỉnh tiếp tục làm thủ hạ cho cháu quận Việp là quận Huy Hoàng Đình Bảo. Khi ấy có người tố cáo ông trước đây từng biển thủ vàng bạc của công. Việc này dây dưa đến cả quận Huy. Nguyễn Hữu Chỉnh bị bắt giam vào ngục và bị tra tấn gần chết, nhưng một mực không thú tội. Cuối cùng ông và quận Huy đều được vô tội. Từ sau vụ này quận Huy càng coi trọng ông hơn.

Quận Huy vào trấn thủ Nghệ An, cử Nguyễn Hữu Chỉnh làm hữu tham quân, đảm trách việc huấn luyện thủy quân đánh giặc biển. Ông đi đánh giặc biển, liên tiếp giành chiến thắng. Sách Hoàng Lê nhất thống chí thuật lại: "Chẳng bao lâu Chỉnh trở thành vô địch trong nghề thuỷ chiến. Ngoài biển, mọi người thường gọi Chỉnh là "con hải ưng"". Khi quận Huy được đổi làm trấn thủ Sơn Nam, Nguyễn Hữu Chỉnh thêo thân chủ ra Sơn Nam, làm quản lãnh đội Tuần hải, thường đem quân đi tuần mặt biển. Sau ông trở lại trấn Nghệ An làm quản lãnh cơ Tiền ninh.

Năm 1782, Tĩnh Đô vương Trịnh Sâm chết, truyền ngôi con thứ 5 tuổi là Điện Đô vương Trịnh Cán. Hoàng Đình Bảo được giao làm phụ chính, quyết định mọi việc trong triều.